package dynamic.dpPack;

import java.util.ArrayList;
import java.util.List;

/**
 * 混合背包
 */
public class MixPack {

    /**
     * int[] s
     * si=−1 表示第 i 种物品只能用1次；
     * si=0 表示第 i 种物品可以用无限次；
     * si>0 表示第 i 种物品可以使用 si 次；
     */
    private int packMixDp(int V, int[] c, int[] w, int[] s) {
        int[] dp = new int[V+1];
        List<Thing> things = new ArrayList<>();
        // 数据更改
        for (int i=1; i<=c.length; i++) {
            if (s[i - 1] <= 0) {
                things.add(new Thing(c[i - 1], w[i - 1], s[i - 1]));
            } else {
                int k;
                for (k = 1; k <= s[i - 1]; k <<= 1) {
                    things.add(new Thing(k * c[i - 1], k * w[i - 1], k * s[i - 1]));
                }
                if (s[i - 1] - k >> 1 > 0) {
                    int num = (s[i - 1] - k >> 1);
                    things.add(new Thing(num * c[i - 1], num * w[i - 1], num * s[i - 1]));
                }
            }
        }
        for (Thing thing: things) {
            // 完全背包处理
            if (thing.getS() == 0) {
                for (int j=thing.getC(); j<=V; j++) {
                    dp[j] = Math.max(dp[j], dp[j-thing.getC()]+thing.getW());
                }
            } else { // 01背包和多重背包按照01背包处理
                for (int j=V; j>=thing.getC(); j--) {
                    dp[j] = Math.max(dp[j], dp[j-thing.getC()]+thing.getW());
                }
            }
        }
        return dp[V];
    }

    class Thing {
        private int c, w, s;
        Thing(int c, int w, int s) {
            this.c = c;
            this.w = w;
            this.s = s;
        }

        public int getC() {
            return c;
        }

        public void setC(int c) {
            this.c = c;
        }

        public int getW() {
            return w;
        }

        public void setW(int w) {
            this.w = w;
        }

        public int getS() {
            return s;
        }

        public void setS(int s) {
            this.s = s;
        }
    }

    public static void main(String[] args) {
        //int[] c = new int[]{2, 3, 4, 5, 1};  // 费用/重量
        //int[] w = new int[]{6, 5, 4, 3, 2};  // 价值
        //int[] n = new int[]{-1, 0, 2, 2, 2};  // 数量
        //int V = 4;  // 背包容量

        int[] c = new int[]{1, 2, 3, 4};
        int[] w = new int[]{2, 4, 4, 5};
        int[] n = new int[]{-1, 1, 0, 2};
        int V = 5;
        MixPack mixPack = new MixPack();
        int ans = mixPack.packMixDp(V, c, w, n);
        System.out.println("dp ans:"+ans);
    }
}
